import java.util.HashMap;

public class longestConsecutive {
    /**
     * 最长连续序列（无序）
     * @author ShakeJ
     * @date 2024/3/18
     */
    /**
     * 给定一个未排序的整数数组，找出数字连续的最长序列（不要求序列元素在原数组中连续）长度
     * 设计并实现时间复杂度O(n)，想到是是哈希表前后窗口进行解答
     */
    public static int method(int[] nums){
        // key表示当前遍历的元素，对应的value为包含当前元素的子序列的长度
        HashMap<Integer, Integer>map = new HashMap<>();
        int ans = 0;
        for(int num :nums){ //时间复杂度为O（n）
            if(!map.containsKey(num)){
                // left 代表的是左子区间的长度，左连续区间的长度;右区间也是一样
                int left = map.getOrDefault(num - 1,0);
                int right = map.getOrDefault(num + 1,0);
                // 当前连续区间的长度
                int curLen = left + right + 1; //
                ans = Math.max(ans, curLen);
                // 将当前遍历过的元素放入窗口curLen中
                map.put(num, 0);
                map.put(num- left,curLen);
                map.put(num+ right,curLen);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int []a={2,1,3,5,4,6};
        System.out.println(method(a));
    }
}
